{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Capacity To Ship Packages Within D Days"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shipWithinDays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在 D 天内送达包裹的能力"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>传送带上的包裹必须在 <code>days</code> 天内从一个港口运送到另一个港口。</p>\n",
    "\n",
    "<p>传送带上的第 <code>i</code>&nbsp;个包裹的重量为&nbsp;<code>weights[i]</code>。每一天，我们都会按给出重量（<code>weights</code>）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。</p>\n",
    "\n",
    "<p>返回能在 <code>days</code> 天内将传送带上的所有包裹送达的船的最低运载能力。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>weights = [1,2,3,4,5,6,7,8,9,10], days = 5\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>\n",
    "船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：\n",
    "第 1 天：1, 2, 3, 4, 5\n",
    "第 2 天：6, 7\n",
    "第 3 天：8\n",
    "第 4 天：9\n",
    "第 5 天：10\n",
    "\n",
    "请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>weights = [3,2,2,4,1,4], days = 3\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：\n",
    "第 1 天：3, 2\n",
    "第 2 天：2, 4\n",
    "第 3 天：1, 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>weights = [1,2,3,1,1], days = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "第 1 天：1\n",
    "第 2 天：2\n",
    "第 3 天：3\n",
    "第 4 天：1, 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= days &lt;= weights.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= weights[i] &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [capacity-to-ship-packages-within-d-days](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [capacity-to-ship-packages-within-d-days](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8,9,10]\\n5', '[3,2,2,4,1,4]\\n3', '[1,2,3,1,1]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 二分+贪心\n",
    "        # 确定边界，边界不一定是idx\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            need, cur = 1, 0\n",
    "            for weight in weights:\n",
    "                if cur + weight > mid:\n",
    "                    need += 1\n",
    "                    cur = 0\n",
    "                cur += weight\n",
    "            if need <= days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shipWithinDays(self, weights, D):\n",
    "        \"\"\"\n",
    "        :type weights: List[int]\n",
    "        :type D: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        def getDays(weights,capacity):\n",
    "\n",
    "            s = 0\n",
    "            t = []\n",
    "            result = []\n",
    "\n",
    "            for i in weights:\n",
    "\n",
    "                if s + i <= capacity:\n",
    "                    s += i\n",
    "                    t.append(i)\n",
    "                else:\n",
    "\n",
    "                    s = i\n",
    "                    result.append(t)\n",
    "                    t = []\n",
    "                    t.append(i)\n",
    "\n",
    "            if len(t) > 0:\n",
    "                result.append(t)\n",
    "\n",
    "            return result\n",
    "\n",
    "        if D == 1:\n",
    "            return sum(weights)\n",
    "\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "\n",
    "        result = []\n",
    "\n",
    "        while left < right:\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            t =  getDays(weights, mid)\n",
    "\n",
    "            day = len( t )\n",
    "\n",
    "            if day <= D:\n",
    "                result.append(mid)\n",
    "                right = mid\n",
    "\n",
    "            elif day > D:\n",
    "                left = mid + 1\n",
    "\n",
    "        return min(result)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], D: int) -> int:\n",
    "        n = len(weights)\n",
    "        capacity_down = max(weights)\n",
    "        capacity_up = sum(weights)\n",
    "\n",
    "        def leastDay(capa):\n",
    "            day = 0\n",
    "            wei_day = 0\n",
    "            for i in range(n):\n",
    "                wei_day += weights[i]\n",
    "                if wei_day > capa:\n",
    "                    day += 1\n",
    "                    wei_day = weights[i]\n",
    "            day += 1\n",
    "            return day\n",
    "\n",
    "        def biSearch(left, right):\n",
    "            dleft = leastDay(left)\n",
    "            if dleft <= D:\n",
    "                return left\n",
    "            dright = leastDay(right)\n",
    "            mid = left + (right-left)//2\n",
    "            dmid = leastDay(mid)\n",
    "            if dmid <= D:\n",
    "                return biSearch(left, mid)\n",
    "            else:\n",
    "                return biSearch(mid+1, right)\n",
    "        \n",
    "        return biSearch(capacity_down, capacity_up)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shipWithinDays(self, weights, D):\n",
    "        \"\"\"\n",
    "        :type weights: List[int]\n",
    "        :type D: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        def getDays(weights,capacity):\n",
    "\n",
    "            s = 0\n",
    "            t = []\n",
    "            result = []\n",
    "\n",
    "            for i in weights:\n",
    "\n",
    "                if s + i <= capacity:\n",
    "                    s += i\n",
    "                    t.append(i)\n",
    "                else:\n",
    "\n",
    "                    s = i\n",
    "                    result.append(t)\n",
    "                    t = []\n",
    "                    t.append(i)\n",
    "\n",
    "            if len(t) > 0:\n",
    "                result.append(t)\n",
    "\n",
    "            return result\n",
    "\n",
    "        if D == 1:\n",
    "            return sum(weights)\n",
    "\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "\n",
    "        while left < right:\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            t =  getDays(weights, mid)\n",
    "\n",
    "            day = len( t )\n",
    "\n",
    "            if day <= D:\n",
    "                right = mid\n",
    "\n",
    "            elif day > D:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, n):\n",
    "        each_day_weight = 0\n",
    "        day = 0\n",
    "        for w in self.weights:\n",
    "            each_day_weight += w\n",
    "            if each_day_weight > n:\n",
    "                each_day_weight = w\n",
    "                day += 1\n",
    "        day += 1\n",
    "        if day > self.days:\n",
    "            return False\n",
    "        return True \n",
    "        \n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        self.weights = weights\n",
    "        self.days = days\n",
    "        start_num = max(max(weights), sum(weights) // days)\n",
    "        preSum = [0] * (len(weights) + 1)\n",
    "        for i in range(1, len(preSum)):\n",
    "            preSum[i] = preSum[i - 1] + weights[i - 1]\n",
    "        for i in range(1, len(preSum)):\n",
    "            if preSum[i] >= start_num:\n",
    "                left = i\n",
    "                break\n",
    "        right = len(preSum) - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            judge_bool = self.judge(preSum[mid])\n",
    "            if judge_bool == True:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        for i in range(max(start_num, preSum[left - 1] + 1), preSum[left] + 1):\n",
    "            if self.judge(i):\n",
    "                return i\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights, D):\n",
    "        minq = max(weights)\n",
    "        maxq = sum(weights)\n",
    "        def binS(l,r):\n",
    "            #print(l,r)\n",
    "            if l > r:\n",
    "                return l\n",
    "            day = 0\n",
    "            w = (l+r)//2\n",
    "            i = 0\n",
    "            while i < len(weights):\n",
    "                w -= weights[i]\n",
    "                if w < 0:\n",
    "                    day += 1\n",
    "                    w = (l+r)//2-weights[i]\n",
    "                i += 1\n",
    "            day += 1\n",
    "            #print((l+r)//2,day,\"oij\")\n",
    "            if day == D:\n",
    "                #print(\"cdfdsfdsf\",(l+r)//2,l,r+1)\n",
    "                for x in range(l,r+1):\n",
    "                    xw = x\n",
    "                    xday = 0\n",
    "                    ii = 0\n",
    "                    while ii < len(weights):\n",
    "                        xw -= weights[ii]\n",
    "                        if xw < 0:\n",
    "                            xday += 1\n",
    "                            xw = x - weights[ii]\n",
    "                        ii += 1\n",
    "                    xday += 1\n",
    "                    if xday == D:\n",
    "                        return x\n",
    "\n",
    "            elif day > D:\n",
    "                return binS((l+r)//2+1, r)\n",
    "            else:\n",
    "                return binS(l, (l+r)//2-1)\n",
    "        return binS(minq,maxq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        max_num, cum_sum = weights[0], [0] * len(weights)\n",
    "        cum_sum[0] = weights[0]\n",
    "        for i in range(1, len(weights)):\n",
    "            cum_sum[i] = cum_sum[i-1] + weights[i]\n",
    "            max_num = max(max_num, weights[i])\n",
    "        low, high = max(math.ceil(cum_sum[-1]/days), max_num), cum_sum[-1]\n",
    "        while low < high:\n",
    "            l0, l, prev_sum = 0, 0, 0\n",
    "            middle = low + (high - low) // 2\n",
    "            for _ in range(days-1):\n",
    "                if l0 == len(weights):\n",
    "                    break\n",
    "                l0, r = l, len(weights)\n",
    "                while l < r:\n",
    "                    mid = l + (r-l)//2\n",
    "                    if cum_sum[mid] - prev_sum > middle:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                prev_sum = cum_sum[min(max(l-1, l0), len(weights)-1)]\n",
    "            if cum_sum[-1] - cum_sum[min(max(l-1, l0), len(weights)-1)] <= middle:\n",
    "                high = middle\n",
    "            else:\n",
    "                low = middle + 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        weightsPre = [0] * (len(weights) + 1)\n",
    "        for i, w in enumerate(weights, 1):\n",
    "            weightsPre[i] = weightsPre[i - 1] + w\n",
    "        # print('weightsPre: ', weightsPre)\n",
    "        \n",
    "        # limit is the assume ship weight capacity, check under this status, if succeed\n",
    "        def check(m: int) -> bool:\n",
    "            # in days times, shipped all weights\n",
    "            usedDay = 0\n",
    "            shippedWeight = 0\n",
    "            i = 1\n",
    "            while i < len(weightsPre):\n",
    "                if weightsPre[i] - shippedWeight <= m: # can ship today\n",
    "                    i += 1\n",
    "                else: # today no more package\n",
    "                    usedDay += 1\n",
    "                    shippedWeight = weightsPre[i - 1]\n",
    "            # print('m usedDay: ', m, usedDay)\n",
    "            return usedDay < days\n",
    "\n",
    "\n",
    "        \n",
    "        l, r = max(weights), sum(weights)\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], D: int) -> int:\n",
    "        left  = max(weights) \n",
    "        right = sum(weights)\n",
    "        def check(w, weigths, D):\n",
    "            count_d = 0\n",
    "            sum_w = 0\n",
    "            for i in range(len(weights)):\n",
    "                if sum_w+weights[i]>w:\n",
    "                    count_d += 1\n",
    "                    sum_w = 0\n",
    "                sum_w += weights[i]\n",
    "            else:\n",
    "                if sum_w>0:\n",
    "                    count_d += 1\n",
    "            return count_d<=D\n",
    "            \n",
    "\n",
    "        def binsearch(l, r):\n",
    "            if r==l:# 左界结束\n",
    "                return l\n",
    "            if r-l==1: # 右界结束\n",
    "                return l if check(l, weights, D) else r\n",
    "            mid = (l+r)//2\n",
    "            is_check = check(mid, weights, D)\n",
    "            print(mid, is_check)\n",
    "            return binsearch(l, mid) if is_check else binsearch(mid, r)\n",
    "        \n",
    "        return binsearch(left, right)\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 确定二分查找左右边界\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # need 为需要运送的天数\n",
    "            # cur 为当前这一天已经运送的包裹重量之和\n",
    "            need, cur = 1, 0\n",
    "            for weight in weights:\n",
    "                if cur + weight > mid:\n",
    "                    need += 1\n",
    "                    cur = 0\n",
    "                cur += weight\n",
    "            \n",
    "            if need <= days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, weights, x):\n",
    "        wlen = len(weights)\n",
    "        day = 1\n",
    "        idx = 0\n",
    "        sum = 0\n",
    "        while idx < wlen:\n",
    "            if sum + weights[idx] <= x:\n",
    "                sum += weights[idx]\n",
    "            else:\n",
    "                sum = weights[idx]\n",
    "                day += 1\n",
    "            idx += 1\n",
    "\n",
    "        return day\n",
    "\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        \"\"\"\n",
    "        传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。\n",
    "        传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。\n",
    "        我们装载的重量不会超过船的最大运载重量。\n",
    "        返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。\n",
    "        :param weights:\n",
    "        :param days:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        # x：运载力， f(x)需要传输的时间,递减的关系，找左边界\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            cur_f = self.f(weights, mid)\n",
    "            # print(mid, cur_f)\n",
    "            if cur_f == days:\n",
    "                right = mid\n",
    "            # elif cur_f > days:\n",
    "            #     left = mid + 1\n",
    "            elif cur_f < days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights, days: int) -> int:\n",
    "        def countDay(weights, cap):\n",
    "            cnt_day = 0\n",
    "            tmp = 0\n",
    "            for wei in weights:\n",
    "                tmp += wei\n",
    "                if tmp > cap:\n",
    "                    cnt_day += 1\n",
    "                    tmp = wei\n",
    "            return cnt_day + 1\n",
    "\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            res = countDay(weights, mid)\n",
    "            if res > days:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left\n",
    "    # leetcode submit region end(Prohibit modification and deletion)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], D: int) -> int:\n",
    "        max_w, sum_w = max(weights), sum(weights)\n",
    "        l, r = max(max_w, sum_w // D), sum_w\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if self.check(weights, mid, D):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r\n",
    "\n",
    "    def check(self, ws, t, d):\n",
    "        n = len(ws)\n",
    "        i = cnt = 1\n",
    "        total = ws[0]\n",
    "        while i < n:\n",
    "            while i < n and total + ws[i] <= t:\n",
    "                total += ws[i]\n",
    "                i += 1\n",
    "            total = 0\n",
    "            cnt += 1\n",
    "        return cnt - 1 <= d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        start = max(sum(weights)//len(weights), max(weights))\n",
    "        end = sum(weights)\n",
    "        while start < end:\n",
    "            mid = (start+end) // 2\n",
    "            if self.isOk(weights, mid, days):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "            print(start, mid, end)\n",
    "            \n",
    "        return end\n",
    "    \n",
    "    def isOk(self, weights, mid, days):\n",
    "        curWeight = 0\n",
    "        count  = 1\n",
    "        for i in range(len(weights)):\n",
    "            curWeight += weights[i]\n",
    "            if curWeight > mid:\n",
    "                count += 1\n",
    "                curWeight = weights[i]\n",
    "            i += 1\n",
    "        print(count)\n",
    "        if count <= days:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max((sum(weights)+days-1)//days, max(weights))\n",
    "        right = sum(weights)\n",
    "        mid = 0\n",
    "        while right>left:\n",
    "            mid = (left+right)//2\n",
    "\n",
    "            t = days\n",
    "            w = 0\n",
    "            for n in weights:\n",
    "                w += n \n",
    "                if w > mid:\n",
    "                    w = n\n",
    "                    t -= 1                    \n",
    "                if t <= 0:\n",
    "                    break\n",
    "            print(left, mid, right, t)\n",
    "            if t <= 0:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def is_vaild(x,days):\n",
    "            res = 0\n",
    "            left = 0\n",
    "            presum = 0\n",
    "\n",
    "            while left < len(weights):\n",
    "                presum += weights[left]\n",
    "                if presum > x:\n",
    "                    res += 1\n",
    "                    presum = 0\n",
    "                else:\n",
    "                    left += 1\n",
    "            if presum <= x:\n",
    "                res += 1\n",
    "            return res <= days\n",
    "        \n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in weights:\n",
    "            left = max(left,i)\n",
    "            right += i\n",
    "    \n",
    "        # 二分寻求答案 \n",
    "        while left <= right:\n",
    "            mid = (left+right) >> 1\n",
    "            if is_vaild(mid,days):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.pass_target(weights, days, mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def pass_target(self, weights: List[int], days: int, carriage: int) -> bool:\n",
    "        take = 0\n",
    "        day = 0\n",
    "        for w in weights:\n",
    "            take += w\n",
    "            if take > carriage:\n",
    "                take = w\n",
    "                day += 1\n",
    "                if day > days:\n",
    "                    return False\n",
    "        if take > 0:\n",
    "            day += 1\n",
    "        if day <= days:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        #肯定最低要运送一个max(weights)，不然都运输不了,一次全部运输完sum(weights)\n",
    "        left,right=max(weights),sum(weights)\n",
    "        res=0\n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "            #默认第一天开始\n",
    "            cnt=1\n",
    "            tmp=0\n",
    "            for w in weights:\n",
    "                tmp+=w\n",
    "                #一旦超出运量，加一天，然后下一天的开始就是w\n",
    "                if tmp>mid:\n",
    "                    tmp=w \n",
    "                    cnt+=1\n",
    "            #比要求的更快，可以减少点运载能力\n",
    "            if cnt<=days:\n",
    "                res=mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt, sums = 1, 0\n",
    "            for weight in weights:\n",
    "                if sums + weight > mid:\n",
    "                    cnt += 1\n",
    "                    sums = 0\n",
    "                sums += weight\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        mi = max(weights)\n",
    "        ma = sum(weights)\n",
    "        # 二分法查找，如果在规定天数内能运完，那么继续遍历，直到找到那个不能运完的那天，找到之后在加加，找到第一次能运完的那个载量，放回载量-1\n",
    "        while mi < ma:\n",
    "            m_temp = (ma + mi) // 2\n",
    "            day = self.yes_yun(weights, m_temp) \n",
    "            if day > days:\n",
    "                mi = m_temp + 1\n",
    "            else:\n",
    "                ma = m_temp\n",
    "        return mi\n",
    "\n",
    "\n",
    "    def yes_yun(self, w, m):\n",
    "        n = 0\n",
    "        tm = 0\n",
    "        for i in w:\n",
    "            tm += i\n",
    "            if tm > m:\n",
    "                tm = i\n",
    "                n += 1\n",
    "        n += 1\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def f(weights, max_weight):\n",
    "            count = 0\n",
    "            cur = 0\n",
    "            for i in range(len(weights)):\n",
    "                cur += weights[i]\n",
    "                if cur > max_weight:\n",
    "                    cur = weights[i]\n",
    "                    count += 1\n",
    "            if cur > 0: count+=1\n",
    "            return count\n",
    "        #print(f(weights,5))\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if days < f(weights, mid):\n",
    "                left = mid + 1\n",
    "            elif days > f(weights, mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights) + 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            use_days = self.f(mid, weights)\n",
    "            if use_days == days:\n",
    "                right = mid\n",
    "            elif use_days > days:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def f(self, mid, weights):\n",
    "        tmp = mid\n",
    "        use_day = 1\n",
    "        index = 0\n",
    "        while index < len(weights):\n",
    "            weight = weights[index]\n",
    "            if tmp >= weight:\n",
    "                tmp -= weight\n",
    "            else:\n",
    "                tmp = mid\n",
    "                index -= 1\n",
    "                use_day += 1\n",
    "            index += 1\n",
    "        return use_day"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt, sums = 1, 0\n",
    "            for weight in weights:\n",
    "                if sums + weight > mid:\n",
    "                    cnt += 1\n",
    "                    sums = 0\n",
    "                sums += weight\n",
    "\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt, sums = 1, 0\n",
    "            for wt in weights:\n",
    "                if sums + wt > mid:\n",
    "                    sums = 0\n",
    "                    cnt += 1\n",
    "                sums += wt\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left,right = max(weights),sum(weights)\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            day=1;tmp=0\n",
    "            for w in weights:\n",
    "                if tmp+w>mid:\n",
    "                    day+=1\n",
    "                    tmp=w\n",
    "                else:\n",
    "                    tmp+=w\n",
    "            if day>days:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def f(weights, max_weight):\n",
    "            need, cur = 1, 0\n",
    "            for weight in weights:\n",
    "                if cur + weight > max_weight:\n",
    "                    need += 1\n",
    "                    cur = 0\n",
    "                cur += weight\n",
    "            return need\n",
    "        #print(f(weights,5))\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if days < f(weights, mid):\n",
    "                left = mid + 1\n",
    "            elif days > f(weights, mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left=max(weights)\n",
    "        right=sum(weights)\n",
    "        def fs(x):\n",
    "            day=1\n",
    "            cur=0\n",
    "            cap=x\n",
    "            for weight in weights:\n",
    "                if cur+weight>cap:\n",
    "                    day+=1\n",
    "                    cur=0\n",
    "                cur+=weight\n",
    "            return day<=days\n",
    "        return bisect.bisect_left(range(left,right),True,key=fs)+left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while(left < right):\n",
    "            mid = (left + right) // 2\n",
    "            \n",
    "            curr = 0\n",
    "            day = 1\n",
    "            for pack in weights:\n",
    "                if curr + pack > mid:\n",
    "                    curr = 0\n",
    "                    day += 1\n",
    "\n",
    "                curr += pack\n",
    "\n",
    "            if day <= days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "            \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 二分查找\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            sums, cnt = 0, 1\n",
    "            for wt in weights:\n",
    "                if sums + wt > mid:\n",
    "                    cnt += 1\n",
    "                    sums = 0\n",
    "                sums += wt\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if self.check(weights,mid) <= days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def check(self,weights,mid):\n",
    "        d = 1\n",
    "        current = 0\n",
    "        for w in weights:\n",
    "            current += w\n",
    "            if current > mid:\n",
    "                d += 1\n",
    "                current = w\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        l = max(weights)\n",
    "        r = sum(weights)\n",
    "        while l < r:\n",
    "            m = (l+r)//2\n",
    "            d = 1\n",
    "            cur = 0\n",
    "            for i in weights:\n",
    "                if cur+i>m:\n",
    "                    d+=1\n",
    "                    cur=0\n",
    "                cur += i\n",
    "            if d <= days:\n",
    "                r=m\n",
    "            else:\n",
    "                l = m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def canShip(capacity):\n",
    "            days_required = 1\n",
    "            current_load = 0\n",
    "            for weight in weights:\n",
    "                if current_load + weight > capacity:\n",
    "                    days_required += 1\n",
    "                    current_load = 0\n",
    "                current_load += weight\n",
    "            return days_required <= days\n",
    "        \n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if canShip(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = 0\n",
    "        right = sum(weights)\n",
    "\n",
    "        def can_do_this(capacity):\n",
    "            if max(weights) > capacity:\n",
    "                return False\n",
    "            need = 0\n",
    "            i = 0\n",
    "            count = 0\n",
    "            while i < len(weights):\n",
    "                while i < len(weights) and count < capacity:\n",
    "                    count += weights[i]\n",
    "                    if count >= capacity:\n",
    "                        need += 1\n",
    "                        if count == capacity:\n",
    "                            i += 1\n",
    "                        count = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        i += 1\n",
    "            if count != 0:\n",
    "                need += 1\n",
    "            if need <= days:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if can_do_this(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        if can_do_this(left):\n",
    "            return left\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        def calDays(target):\n",
    "            res= 1 \n",
    "            cnt = 0\n",
    "            for x in weights:\n",
    "                if cnt + x > target:\n",
    "                    cnt = x\n",
    "                    res += 1\n",
    "                else:\n",
    "                    cnt += x\n",
    "            return res\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            t = calDays(mid)\n",
    "            if t > days:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt, sums = 1, 0\n",
    "            for wt in weights:\n",
    "                if sums + wt > mid:\n",
    "                    cnt += 1\n",
    "                    sums = 0\n",
    "                sums += wt\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        low, high = max(weights), sum(weights) #最大运载量的范围\n",
    "        while low < high: #当low >=high 跳出循环\n",
    "            mid = (low + high)//2\n",
    "\n",
    "            temp = 0\n",
    "            day =1\n",
    "            for w in weights: #模拟一条船的货运过程\n",
    "                temp += w\n",
    "                if temp > mid: #另一天来运\n",
    "                    day += 1\n",
    "                    temp = w\n",
    "            if day > days: #超时了，需要更大的荷载的船\n",
    "                low = mid +1\n",
    "            elif day <=days:#适当减少荷载\n",
    "                high =mid\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def getDays(wordload):\n",
    "            d = 1\n",
    "            count = 0\n",
    "            for w in weights:\n",
    "                if count + w > wordload:\n",
    "                    count = w\n",
    "                    d += 1\n",
    "                else:\n",
    "                    count += w \n",
    "            return d \n",
    "        \n",
    "        l, r = max(weights), sum(weights)\n",
    "        res = r\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            daysNeed = getDays(mid)\n",
    "            # print(l, mid, r, daysNeed)\n",
    "            if daysNeed <= days:\n",
    "                r = mid - 1\n",
    "                res = min(res, mid) # 答案可能出现在 用的天数小于需要天数的情况内\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)#left的设置\n",
    "        def get_days(weights: List[int], mid: int) -> int:\n",
    "            res, cur = 1, 0 # res一定要为1\n",
    "            for weight in weights:\n",
    "                if cur + weight > mid:#这个的设置\n",
    "                    res += 1\n",
    "                    cur = 0\n",
    "                cur += weight  \n",
    "            return res     \n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            # print(f\"left = {left}, right = {right}, get_days = {get_days(weights, mid)}\")\n",
    "            if get_days(weights, mid) <= days:\n",
    "                right = mid#<=的时候可能是答案\n",
    "            else:\n",
    "                left = mid + 1#>的时候一定不是答案\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        l ,r = max(weights),sum(weights)\n",
    "\n",
    "        while l<=r:\n",
    "            mid = l+((r-l)>>1)\n",
    "            need,cur=1,0\n",
    "            for weight in weights:\n",
    "                if cur + weight > mid:\n",
    "                    need+=1\n",
    "                    cur=0\n",
    "                cur+=weight\n",
    "            if need>days:\n",
    "                l =mid+1\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "\n",
    "        high = sum(weights)\n",
    "        low = max(weights)\n",
    "        n = len(weights)\n",
    "\n",
    "        def can_deliver(x):\n",
    "            y = 0\n",
    "            day = 1\n",
    "            for i in range(n):\n",
    "                y += weights[i]\n",
    "                if y<=x:\n",
    "                    continue \n",
    "                else:\n",
    "                    day += 1\n",
    "                    y = weights[i]\n",
    "            return day<=days\n",
    "        while low<high:\n",
    "            mid = (low+high)//2\n",
    "\n",
    "            if can_deliver(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid+1\n",
    "        \n",
    "        return low \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 需要运送天数关于船的运载能力的函数 单调递减  \n",
    "        def f(weights, x):\n",
    "            n = len(weights)\n",
    "            d = 0\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                cap = x\n",
    "                # 一天内能够装载的包裹(尽可能多装)\n",
    "                while i < n:\n",
    "                    if cap < weights[i]:\n",
    "                        break\n",
    "                    else:\n",
    "                        cap -= weights[i]\n",
    "                        i += 1\n",
    "                d += 1\n",
    "            return d \n",
    "\n",
    "        # 左边界\n",
    "        left, right = max(weights), sum(weights)+1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if f(weights, mid) <= days: # 符合要求\n",
    "                right = mid \n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 确定二分查找左右边界\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # need 为需要运送的天数\n",
    "            # cur 为当前这一天已经运送的包裹重量之和\n",
    "            need, cur = 1, 0\n",
    "            for weight in weights:\n",
    "                if cur + weight > mid:\n",
    "                    need += 1\n",
    "                    cur = 0\n",
    "                cur += weight\n",
    "            \n",
    "            if need <= days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def check(x:int) -> bool:\n",
    "            cnt = 1\n",
    "            y = 0\n",
    "            for weight in weights:\n",
    "                if y + weight > x:\n",
    "                    y = weight\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    y += weight\n",
    "            return cnt <= days\n",
    "        l,r = max(weights),sum(weights)\n",
    "        while l < r:\n",
    "            m = (l+r)//2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def cal_days(weights, x):\n",
    "            days = 0\n",
    "            i = 0\n",
    "            while i < len(weights):\n",
    "                cap = x\n",
    "                while i < len(weights):\n",
    "                    if cap < weights[i]:\n",
    "                        break\n",
    "                    else:\n",
    "                        cap -= weights[i]\n",
    "                        i += 1\n",
    "                days += 1\n",
    "            return days\n",
    "\n",
    "        l, r = max(weights), sum(weights)\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + (r - l)//2\n",
    "            if cal_days(weights, mid) <= days:\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 二分查找\n",
    "        left, right = max(weights), sum(weights)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            days_tmp = 1\n",
    "            cur = 0\n",
    "            for weight in weights:\n",
    "                if cur + weight > mid:\n",
    "                    days_tmp += 1\n",
    "                    cur = 0\n",
    "                cur += weight\n",
    "            \n",
    "            if days_tmp <= days:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getDayWithWeight(self, maxWeight):\n",
    "        i = 0\n",
    "        tempSum = 0\n",
    "        count = 1\n",
    "        \n",
    "        for i in range(len(self.weights)):\n",
    "            if tempSum + self.weights[i] <= maxWeight:\n",
    "                tempSum += self.weights[i]\n",
    "            else:\n",
    "                count += 1\n",
    "                tempSum = self.weights[i]\n",
    "        return count <= self.days\n",
    "        \n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # print(list(map(int, list(range(max(weights), sum(weights)+1)))))\n",
    "        # nonlocal weights\n",
    "        self.weights = weights\n",
    "        self.days = days\n",
    "\n",
    "        # theRange = list(range(max(weights), sum(weights)+1))\n",
    "        # print(theRange)\n",
    "        l = max(weights)\n",
    "        r = sum(weights)+1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if self.getDayWithWeight(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r\n",
    "            \n",
    "        tarWei = 0\n",
    "        \n",
    "        theList = list(map(self.getDayWithWeight, theRange))\n",
    "        print(theList)\n",
    "        print(days)\n",
    "        idx = bisect.bisect_left(theList, -days)\n",
    "        print(idx)\n",
    "        return theRange[idx]\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights) # 最大承重\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            cnt = 1 # 花费的时间\n",
    "            temp = 0 # 承重\n",
    "            for w in weights:\n",
    "                if temp + w <=mid:\n",
    "                   temp += w\n",
    "                else:\n",
    "                    temp = w\n",
    "                    cnt += 1\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right + 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def check_possi(out):\n",
    "            day_cost = 1\n",
    "            cur = 0\n",
    "            for val in weights:\n",
    "                cur += val\n",
    "                if cur > out:\n",
    "                    day_cost += 1\n",
    "                    cur = val\n",
    "                    if day_cost > days:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        LOWER = max(weights)\n",
    "        UPPER = sum(weights)\n",
    "        out = (LOWER + UPPER) // 2\n",
    "        \n",
    "        while out > LOWER:\n",
    "            if check_possi(out):\n",
    "                UPPER = out\n",
    "            else:\n",
    "                LOWER = out\n",
    "            out = (LOWER + UPPER) // 2\n",
    "\n",
    "        if check_possi(out):\n",
    "            return out\n",
    "        else:\n",
    "            return UPPER\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        # DP: O(n^2), exceed time limit\n",
    "\n",
    "        val_dict = {}\n",
    "        l = len(weights)\n",
    "        \n",
    "        def DP(i, days):\n",
    "            if (i, days) in val_dict.keys():\n",
    "                return val_dict[(i, days)]\n",
    "            elif days == 1:\n",
    "                out = sum(weights[i:])\n",
    "            elif days >= l - i:\n",
    "                out = max(weights[i:]) \n",
    "            else:\n",
    "                cur = 0\n",
    "                out = float('inf')\n",
    "                for j in range(i, l-1):\n",
    "                    cur += weights[j]\n",
    "                    out_sub = DP(j+1, days - 1)\n",
    "                    out = min(out, max(out_sub, cur))\n",
    "                    if cur >= out_sub:\n",
    "                        break\n",
    "            val_dict[(i, days)] = out\n",
    "            return out\n",
    "\n",
    "        out = DP(0, days)\n",
    "        print(val_dict)\n",
    "        return out\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        def DP(i, days):\n",
    "            if (i, days) in val_dict.keys():\n",
    "                out = val_dict[(i, days)]\n",
    "            elif days == 1:\n",
    "                out = sum(weights[:i])\n",
    "            elif days >= i:\n",
    "                out = max(weights[:i])\n",
    "            else:\n",
    "                out = float('inf')\n",
    "                for j in range(i-1, 0, -1):\n",
    "                    cur = sum(weights[j:i])\n",
    "                    out_sub = DP(j, days - 1)\n",
    "                    out = min(out, max(cur, out_sub))\n",
    "                    if cur >= out_sub:\n",
    "                        #print(j, i, cur)\n",
    "                        break\n",
    "            val_dict[(i, days)] = out\n",
    "            return out\n",
    "\n",
    "        out = DP(l, days)\n",
    "        #print(val_dict)\n",
    "        return out\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def getDays(wordload):\n",
    "            d = 1\n",
    "            count = 0\n",
    "            for w in weights:\n",
    "                if count + w > wordload:\n",
    "                    count = w\n",
    "                    d += 1\n",
    "                else:\n",
    "                    count += w \n",
    "            return d \n",
    "        \n",
    "        l, r = max(weights), sum(weights)\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            daysNeed = getDays(mid)\n",
    "            # print(l, mid, r, daysNeed)\n",
    "            if daysNeed <= days: # 用的天数比需要的少或者相等\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def get_count(x):\n",
    "            count = 1\n",
    "            total = 0\n",
    "            for weight in weights:\n",
    "                if total + weight > x:\n",
    "                    count += 1\n",
    "                    total = weight\n",
    "                else:\n",
    "                    total += weight\n",
    "            return count\n",
    "\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if get_count(mid) > days:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        r = sum(weights)\n",
    "        l = max(weights)\n",
    "\n",
    "        def check(max_load):\n",
    "            loading = 0\n",
    "            need_days = 1\n",
    "            for i in range(len(weights)):\n",
    "                loading = loading + weights[i]\n",
    "                if loading > max_load:\n",
    "                    loading = weights[i]\n",
    "                    need_days += 1\n",
    "                if need_days > days:\n",
    "                    return False\n",
    "            return True \n",
    "        \n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        minCapacity = max(weights)\n",
    "        maxCapacity = sum(weights)\n",
    "        ans = -1\n",
    "\n",
    "        def isValid(mid, days):\n",
    "            cnt = 0\n",
    "            curSum = 0\n",
    "            for weight in weights:\n",
    "                curSum += weight\n",
    "                if curSum > mid:\n",
    "                    curSum = weight\n",
    "                    cnt += 1\n",
    "            cnt += 1\n",
    "            return cnt <= days\n",
    "\n",
    "\n",
    "        while minCapacity <= maxCapacity:\n",
    "            mid = (maxCapacity + minCapacity) // 2\n",
    "            if isValid(mid, days):\n",
    "                ans = mid\n",
    "                maxCapacity = mid - 1\n",
    "            else:\n",
    "                minCapacity = mid + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            need_day, day_weight = 1, 0\n",
    "            for weight in weights:\n",
    "                if day_weight + weight > mid:\n",
    "                    need_day += 1\n",
    "                    day_weight = 0\n",
    "                day_weight += weight\n",
    "            if need_day <= days: right = mid\n",
    "            else: left = mid + 1\n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if days >= self.f(weights,mid):\n",
    "                right = mid-1\n",
    "            elif days < self.f(weights,mid):\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n",
    "    def f(self,weights,capacity):\n",
    "        days = 0\n",
    "        i = 0\n",
    "        while i < len(weights):\n",
    "            cap = capacity\n",
    "            while i < len(weights):\n",
    "                if cap < weights[i]:\n",
    "                    break\n",
    "                else:\n",
    "                    cap -= weights[i]\n",
    "                    i+=1\n",
    "            days+=1\n",
    "        return days\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def check(w):\n",
    "            w_left=w\n",
    "            days_left=days-1\n",
    "            for i in range(n):\n",
    "                w_i=weights[i]\n",
    "                if w_left>=w_i:\n",
    "                    w_left=w_left-w_i\n",
    "                elif days_left:\n",
    "                    days_left=days_left-1\n",
    "                    w_left=w-w_i\n",
    "                else:\n",
    "                    w=w+1\n",
    "                    w_left=w_left-w_i\n",
    "                    break\n",
    "            if w_left>=0:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        w_max=max(weights)\n",
    "        w_ave=ceil(sum(weights)//days)\n",
    "        left=max(w_max,w_ave)\n",
    "        right=sum(weights)\n",
    "        n=len(weights)\n",
    "        while(left<right):\n",
    "            w=(left+right)//2\n",
    "            result=check(w)\n",
    "            if result:\n",
    "                right=w\n",
    "            else:\n",
    "                left=w+1\n",
    "        return left\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def check(mid):\n",
    "            d = 1\n",
    "            curr_w = 0\n",
    "            for w in weights:\n",
    "                curr_w += w\n",
    "                if curr_w > mid:\n",
    "                    d += 1\n",
    "                    curr_w = w\n",
    "            return d <= days\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left <= right:\n",
    "            mid = (right + left) //2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if days >= self.f(weights,mid):\n",
    "                right = mid-1\n",
    "            elif days < self.f(weights,mid):\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n",
    "\n",
    "    \n",
    "    def f(self,weights,capacity):\n",
    "        days = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < len(weights):\n",
    "            cap = capacity\n",
    "            while i < len(weights):\n",
    "                if cap < weights[i]:\n",
    "                    break\n",
    "                else:\n",
    "                    cap -= weights[i]\n",
    "                    i+=1\n",
    "            days+=1\n",
    "        return days\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipDays(self, weights, load):\n",
    "        cur_load = 0\n",
    "        day_cnt = 0\n",
    "        for i, w in enumerate(weights):\n",
    "            if w + cur_load > load:\n",
    "                day_cnt += 1\n",
    "                cur_load = 0\n",
    "            cur_load += w\n",
    "        if cur_load > 0:\n",
    "            day_cnt += 1\n",
    "        #print('shipDays', weights, load, day_cnt)\n",
    "        return day_cnt\n",
    "\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        l = max(weights)\n",
    "        r = sum(weights)\n",
    "        while l <= r:\n",
    "            mid = int(l + (r - l) / 2)\n",
    "            mid_day_cnt = self.shipDays(weights, mid)\n",
    "            if mid_day_cnt < days:\n",
    "                r = mid - 1\n",
    "            elif mid_day_cnt > days:\n",
    "                l = mid + 1\n",
    "            elif mid_day_cnt == days:\n",
    "                r = mid - 1\n",
    "        \n",
    "        min_days = self.shipDays(weights, l)\n",
    "        #print(l, min_days, days)\n",
    "        if min_days <= days:\n",
    "            return l\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), math.ceil(len(weights) / days) * max(weights)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.check(weights, days, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left\n",
    "\n",
    "    def check(self, weights: List[int], days: int, load: int) -> bool:\n",
    "        cnt = 1\n",
    "        tot = 0\n",
    "        for n in weights:\n",
    "            tot += n\n",
    "            if tot > load:\n",
    "                cnt += 1\n",
    "                tot = n\n",
    "        if cnt <= days:\n",
    "            return True\n",
    "        else: \n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left, right = max(weights), sum(weights)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.f(weights, mid) <= days:\n",
    "                right = mid - 1\n",
    "            elif self.f(weights, mid) > days:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def f(self, weights, x):\n",
    "        days = 1\n",
    "        capacity = x\n",
    "        for weight in weights:\n",
    "            if weight <= capacity:\n",
    "                capacity -= weight\n",
    "            else:\n",
    "                capacity = x - weight\n",
    "                days += 1\n",
    "        return days"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def get_days(ability):\n",
    "            wei = deque(weights[:])\n",
    "            daily_weight = 0\n",
    "            days = 1\n",
    "\n",
    "            while wei:\n",
    "                to_load = wei.popleft()\n",
    "                if daily_weight+to_load<=ability:\n",
    "                    daily_weight += to_load\n",
    "                else:\n",
    "                    days += 1\n",
    "                    daily_weight = 0\n",
    "                    wei.appendleft(to_load)\n",
    "\n",
    "            return days\n",
    "\n",
    "        left = max(weights)\n",
    "        right = sum(weights)+1\n",
    "\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            res_days = get_days(mid)\n",
    "\n",
    "            if res_days==days:\n",
    "                right = mid\n",
    "            elif res_days<days:\n",
    "                right = mid\n",
    "            elif res_days>days:\n",
    "                left = mid+1\n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights) # 最大承重\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            cnt = 1 # 花费的时间\n",
    "            temp = 0 # 承重\n",
    "            for w in weights:\n",
    "                if temp + w <=mid:\n",
    "                   temp += w\n",
    "                else:\n",
    "                    temp = w\n",
    "                    cnt += 1\n",
    "            if cnt <= days:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right + 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def calcuteWeights(k):\n",
    "            times = 0\n",
    "            temp = 0\n",
    "            for i in range(len(weights)):\n",
    "                temp += weights[i]\n",
    "                if i < (len(weights)-1) and (temp + weights[i+1]) > k:\n",
    "                    times +=1\n",
    "                    temp = 0\n",
    "            return times if temp == 0 else times + 1\n",
    "        \n",
    "        def binarySearch(i, j, target):\n",
    "            while j - i > 3:\n",
    "                mid = (i+j) >> 1\n",
    "                val = calcuteWeights(mid)\n",
    "                print(mid, val)\n",
    "                if val > target: i = mid + 1\n",
    "                else: j = mid\n",
    "            for k in range(i, j+1):\n",
    "                val = calcuteWeights(k)\n",
    "                if val <= target:\n",
    "                    return k\n",
    "            return -1\n",
    "        \n",
    "        total = sum(weights)\n",
    "        i, j = max(weights), total\n",
    "        return binarySearch(i, j, days)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        len_weights = len(weights)\n",
    "\n",
    "        def f(x):\n",
    "            d = 1\n",
    "            c = x\n",
    "            i = 0\n",
    "            while i < len_weights:\n",
    "                if c < weights[i]:\n",
    "                    d += 1\n",
    "                    c = x\n",
    "                else:\n",
    "                    c -= weights[i]\n",
    "                    i += 1\n",
    "            return d\n",
    "        \n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left <= right:\n",
    "            mid = int(left + (right - left) / 2)\n",
    "            if f(mid) > days:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        # 把 n 个数分为 days 组, 最小化 days 组最大值\n",
    "        s = sum(weights)\n",
    "        left, right = max(weights), s + 1\n",
    "        ans = 0\n",
    "        n = len(weights)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            cnt = 1\n",
    "            res = 0\n",
    "            for x in weights:\n",
    "                if res + x > mid:\n",
    "                    cnt += 1\n",
    "                    res = x \n",
    "                else:\n",
    "                    res += x\n",
    "            if cnt <= days:\n",
    "                right = mid\n",
    "                ans = mid \n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        left = max(weights)\n",
    "        right = sum(weights)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            need = self.dayCount(weights, mid)\n",
    "            if need > days:\n",
    "                left = mid + 1\n",
    "            elif need == days:\n",
    "                right = mid - 1\n",
    "            elif need < days:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "\n",
    "    def dayCount(self, weights, capacity):\n",
    "        cur = 0\n",
    "        count = 0\n",
    "        n = len(weights)\n",
    "        for i in range(n):\n",
    "            if cur + weights[i] > capacity:\n",
    "                count += 1\n",
    "                cur = weights[i]\n",
    "            else:\n",
    "                cur += weights[i]\n",
    "        if cur > 0:\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "\n",
    "        def totalDays(weights, days, capability):\n",
    "            totalWeight = 0\n",
    "            countDay = 0\n",
    "\n",
    "            for i in range(len(weights)):\n",
    "                totalWeight = totalWeight + weights[i]\n",
    "                if totalWeight > capability:\n",
    "                    countDay = countDay + 1\n",
    "                    totalWeight = weights[i]\n",
    "                elif totalWeight == capability:\n",
    "                    countDay = countDay + 1\n",
    "                    totalWeight = 0\n",
    "\n",
    "            if totalWeight < capability and totalWeight != 0:\n",
    "                countDay = countDay + 1\n",
    "            \n",
    "            if countDay <= days:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        l = max(weights)\n",
    "        r = sum(weights)\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if totalDays(weights, days, mid) == True:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        start, end = max(weights), sum(weights) # max not min\n",
    "        def is_possible(weight): # entire logic\n",
    "            count_days = 1\n",
    "            cur_load = 0\n",
    "            for w in weights:\n",
    "                if cur_load + w <= weight:\n",
    "                    cur_load += w\n",
    "                else:\n",
    "                   count_days += 1\n",
    "                   cur_load = w\n",
    "            return count_days <= days\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2\n",
    "            if is_possible(mid):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid\n",
    "        return start if is_possible(start) else end\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        def check(mid):\n",
    "            day = 1\n",
    "            count = 0\n",
    "            for weight in weights:\n",
    "                if count + weight > mid:\n",
    "                    count = 0\n",
    "                    day += 1\n",
    "                count += weight\n",
    "            return day <= days\n",
    "\n",
    "        left = max(weights) - 1\n",
    "        right = sum(weights) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            print(mid)\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def enough_capacity(self, capacity, weights, days):\n",
    "        S = 0\n",
    "        require_day = 1\n",
    "        for w in weights:\n",
    "            if S+w>capacity:\n",
    "                S = w\n",
    "                require_day += 1\n",
    "            else:\n",
    "                S += w\n",
    "            if require_day>days:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        \n",
    "        left_bound = max(weights)-1\n",
    "        right_bound = sum(weights)\n",
    "        L, R = 0, right_bound-left_bound\n",
    "        p = (L+R)//2\n",
    "        while(L<R):\n",
    "            if self.enough_capacity(left_bound+p, weights, days):\n",
    "                R = p\n",
    "            else:\n",
    "                L = p\n",
    "            # capacities[L] always dissatisfies, and capacities[R] always satisfies\n",
    "            if R-L==1:\n",
    "                return left_bound+R\n",
    "            p = (L+R)//2\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shipWithinDays(self, weights: List[int], days: int) -> int:\n",
    "        tt = sum(weights)\n",
    "        l, r = min(weights), tt\n",
    "        n = len(weights)\n",
    "\n",
    "        def checkOk(num):\n",
    "            day = 0\n",
    "            idx = 0\n",
    "            i = 0\n",
    "\n",
    "            while i < n:\n",
    "                j = i\n",
    "                wei = 0\n",
    "                while j < n and wei + weights[j] <= num:\n",
    "                    wei += weights[j]\n",
    "                    j += 1\n",
    "                day += 1\n",
    "                if day > days:\n",
    "                    return False\n",
    "                \n",
    "                i = j\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + (r-l)//2\n",
    "            if checkOk(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r # l = r"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
